BOJ_2661_좋은 수열

백트래킹을 사용해서 좋은 수열을 만들어가는 문제
1,2,3을 돌며 작은 숫자부터 수열을 만들어 갈 수 있는지 검사한 후에
최종적으로 만들어진 수열을 반환한다
가장 먼저 만들어진 수열이 최적의 수열이다

파이썬에서는 배열 인덱스에 음수값을 넣어줄 수 있기 때문에
뒤에서부터 i칸 / ix2칸 전부터~i칸을 비교하며 좋은 수열을 만족하는지 검사한다

def is_good(seq):  
    length = len(seq)  
    for i in range(1, length // 2 + 1):  # 정수 나눗셈  
        if seq[-i:] == seq[-2 * i:-i]:  
            return False  
    return True  
  
def find(n):  
    if n == 1:  
        return '1'  
  
    def backtrack(seq):  
        if len(seq) == n:  
            return seq  
  
        for i in '123':  
            new_seq = seq + i  
            if is_good(new_seq):  
                result = backtrack(new_seq)  
                if result:  
                    return result  
  
        return None  
  
    return backtrack('')  
  
  
N = int(input())  
print(find(N))